﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace QQ.InterviewQuestions.BinarySearchTree
{
    internal class BinarySearchTree
    {
        Node root;

        public void Initialize()
        {
            root = new Node(100);
            root.Left = new Node(50);
            root.Left.Left = new Node(25);
            root.Left.Right = new Node(75);
            root.Right = new Node(150);
            root.Right.Left = new Node(125);
            root.Right.Right = new Node(175);
            root.Right.Left.Left = new Node(110);
        }

        public void PreorderTraversal()
        {
            Preorder(root);
        }

        private void Preorder(Node root)
        {
            if (root == null)
            {
                return;
            }

            Console.WriteLine(root.Value);
            Preorder(root.Left);
            Preorder(root.Right);
        }

        public void InorderTraversal()
        {
            Inorder(root);
        }

        private void Inorder(Node root)
        {
            if (root == null)
            {
                return;
            }
            Inorder(root.Left);
            Console.WriteLine(root.Value);
            Inorder(root.Right);
        }

        public void PostorderTraversal()
        {
            Postorder(root);
        }

        private void Postorder(Node root)
        {
            if (root == null)
            {
                return;
            }
            Postorder(root.Left);
            Postorder(root.Right);
            Console.WriteLine(root.Value);
        }

        public void NonRecursiveTraversalPostOrder()
        {
            Stack<Node> s = new Stack<Node>();
            while (root != null || s.Count > 0)
            {
                if (root == null)
                {
                    while (s.Count > 0 && root == s.Peek().Right)
                    {
                        root = s.Peek();
                        s.Pop();
                        Console.WriteLine(root.Value);
                    }
                    root = s.Count > 0 ? null : s.Peek().Right;
                }
                if (root != null)
                {
                    s.Push(root);
                    root = root.Left;
                }
            }
        }

        public void NonRecursiveTraversalInorder()
        {
            Stack<Node> s = new Stack<Node>();
            while (root != null || s.Count > 0)
            {
                if (root == null)
                {
                    root = s.Peek(); s.Pop();
                    Console.WriteLine(root.Value);
                    root = root.Right;
                }
                if (root != null)
                {
                    s.Push(root);
                    root = root.Left;
                }
            }
        }   
    }
}
